[Coding031] 递归 - 最大公约数

欧几里得算法

More coding records

Get the knowledge flowing and circulating! :)

目录

标题：欧几里得算法

概念

整数 正整数

两个整数的最大公约数是能够同时整除它们的最大的正整数。

在数学中，辗转相除法，又称欧几里得算法（英语：Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中（大约公元前300年），所以它是现行的算法中历史最悠久的，而在中国则可以追溯至东汉出现的《九章算术》。

参考：辗转相除法 扩展欧几里得算法

原理

辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。（定义中包含了递归的思想）

例如：欲求252和105的最大公约数。

求解：

• Step1. $252÷105=2(\text{余}42)$$252\div105=2(余42)$ $\iff$$\Leftrightarrow$ $252=2\times 105+$$252=2\times105+$$42$$42$

  从右边的等价式子可以看出：252和105的最大公约数 $\iff$$\Leftrightarrow$ 105和42的最大公约数。

  $$\frac{252}{21}=\frac{2\times 105}{21}+\frac{42}{21}⟹12=2\times 5+2$$

  • 两数中较小的数是105；

  • 两数的余数是42；

• Step2. $105÷42=2(\text{余}21)$$105\div42=2(余21)$ $\iff$$\Leftrightarrow$ $105=2\times 42+21$$105=2\times42+21$

  • 两数中较小的数是42；

  • 两数的余数是21；

• Step3. $42÷21=2(\text{余}0)$$42\div21=2(余0)$ $\iff$$\Leftrightarrow$ $42=2\times 21$$42=2\times21$

  • 两数中较小的数是21；因为余数为0了，所以较小的数和两数相除的余数的最大公约数：21

  • 两数的余数是0。

重要推论

由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如${\displaystyle 21=5\times 105+(-2)\times 252}$${\displaystyle 21=5\times 105+(-2)\times 252}$。这个重要的结论叫做裴蜀定理。

代码

伪代码

递归版

xxxxxxxxxx
5
1
function gcd(a, b)
2
 if b = 0
3
    return a
4
 else
5
    return gcd(b, a mod b)

非递归版

xxxxxxxxxx
6
1
function gcd(a, b)
2
 while b ≠ 0
3
     t ← b
4
     b ← a mod b
5
     a ← t
6
 return a

代码(C语言)

递归版

xxxxxxxxxx
9
1
int gcd(int a, int b)
2
{
3
    int r = a % b;
4

5
    if(r == 0) 
6
        return b;
7
    else 
8
        return gcd(b, r);
9
}

非递归版

xxxxxxxxxx
11
1
int gcd_nr(int a, int b) 
2
{
3
 int r = 1;
4
 while(r != 0) 
5
 {
6
     r = a % b;
7
     a = b;
8
     b = r;
9
 }
10
 return a;
11
}